#include <climits>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

// 77. 组合
// https://leetcode.cn/problems/combinations/description/
class Solution {
    vector<int> path;
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ans;
        dfs(ans, 1, n, k);
        return ans;
    }

    void dfs(vector<vector<int>>& ans, int pos, int n, int k)
    {
        if (path.size() == k)
        {
            ans.push_back(path);
            return;
        }

        for (int i = pos; i<=n; ++i)
        {
            path.push_back(i);
            dfs(ans, i+1, n, k);
            path.pop_back();
        }
    }
};

// 494. 目标和
// https://leetcode.cn/problems/target-sum/
class Solution {
    int ans;
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        dfs(nums, target, 0, 0);
        return ans;
    }

    void dfs(vector<int>& nums, int target, int path, int pos)
    {
        if (pos == nums.size())
        {
            if (path == target)
                ++ans;
            
            return;
        }

        dfs(nums, target, path+nums[pos], pos+1);
        dfs(nums, target, path-nums[pos], pos+1);
    }
};